#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // 先处理特殊的情况
        if (k == 0 || head == nullptr || head->next == nullptr)
        {
            // 直接返回头节点
            return head;
        }
        int n = 1;
        // 头节点
        ListNode *p = head;
        // 求结点的个数n
        while (p -> next != nullptr)
        {
            p = p -> next;
            n++;
        }
        // 循环结束后p指向的是尾节点，现在将p的下一个节点指向头节点
        p ->next = head; // 构成环形链表
        k = k % n;
        int m = n - k;
        p = head;
        head = p -> next;
        while (m > 1)
        {
            m--;
            p = p->next;
            head = p->next;
        }
        // 断开
        p->next = nullptr;
        return head;
        
        
    }
};
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next)
            cout << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}
int main() {
    Solution sol;

    // Test case 1: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, k = 2
    ListNode n1(1), n2(2), n3(3), n4(4), n5(5);
    n1.next = &n2; n2.next = &n3; n3.next = &n4; n4.next = &n5;
    ListNode* res1 = sol.rotateRight(&n1, 2);
    cout << "Test Case 1 Result: ";
    printList(res1);

    return 0;
}